package learn.dfs;

/**
 * 深度优先搜索（递归）
 */
public class DFS_01 {
    /**
     * 目的地
     */
    int B[] = new int[2];

    /**
     * 移动的方向
     */
    int dx[] = {0,0,-1,1};
    int dy[] = {-1,1,0,0};

    /**
     * @param maze 迷宫
     * @param x 起点的X坐标
     * @param y 起点的Y坐标
     * @return 是否可达
     */
    boolean dfs(int maze[][], int x, int y) {
        if (x == B[0] && y == B[1]) {
            return true;
        }

        //标记已经走过
        maze[x][y] = -1;

        //向四个方向进行尝试
        for (int d = 0; d < 4; d++) {
            int i = x + dx[d], j = y + dy[d];

            if (isSafe(maze, i, j) && dfs(maze, i ,j)) {
                return true;
            }
        }

        //尝试所有可能都没到达B
        return false;
    }

    /**
     * 未被遍历且未越界
     * @param maze
     * @param i
     * @param j
     * @return
     */
    private boolean isSafe(int[][] maze, int i, int j) {
        //略
        return true;
    }
}
